#include <iostream>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <vector>
#include <set>
#include <string>

using namespace std;

const unsigned int ASCII_A = 97;
const unsigned int ASCII_Z = ASCII_A + 26;

typedef size_t                            etat_t;
typedef unsigned char                     symb_t;
typedef set< etat_t >                     etatset_t;
typedef vector< vector< etatset_t > >     trans_t;
typedef vector< etatset_t >               epsilon_t;

////////////////////////////////////////////////////////////////////////////////

struct sAutoNDE{
  // caractéristiques
  size_t nb_etats;
  size_t nb_symbs;
  size_t nb_finaux;

  etat_t initial;
  // état initial

  etatset_t finaux;
  // états finaux : finaux_t peut être un int*, un tableau dynamique comme vector<int>
  // ou une autre structure de donnée de votre choix.

  trans_t trans;
  // matrice de transition : trans_t peut être un int***, une structure dynamique 3D comme vector< vector< set<int> > >
  // ou une autre structure de donnée de votre choix.
  
  epsilon_t epsilon; 
  // transitions spontanées : epsilon_t peut être un int**, une structure dynamique 2D comme vector< set<int> >
  // ou une autre structure de donnée de votre choix.
};



////////////////////////////////////////////////////////////////////////////////

bool FromFile(sAutoNDE& at, string path){
 ifstream myfile(path.c_str(), ios::in); 
  //un flux d'entree obtenu à partir du nom du fichier
  string line;
  // un ligne lue dans le fichier avec getline(myfile,line);
  istringstream iss;
  // flux associé à la chaine, pour lire morceau par morceau avec >> (comme cin)
  etat_t s(0), t(0);
  // deux états temporaires
  symb_t a(0);
  // un symbole temporaire

  if (myfile.is_open()){
    // la première ligne donne 'nb_etats nb_symbs nb_finaux'
    do{ 
      getline(myfile,line);
    } while (line.empty() || line[0]=='#');
    // on autorise les lignes de commentaires : celles qui commencent par '#'
    iss.str(line);
    if((iss >> at.nb_etats).fail() || (iss >> at.nb_symbs).fail() || (iss >> at.nb_finaux).fail())
        return false;
    // la deuxième ligne donne l'état initial
    do{ 
      getline (myfile,line);
    } while (line.empty() || line[0]=='#');    
    iss.clear();
    iss.str(line);
    if((iss >> at.initial).fail())
      return -1;
    
    // les autres lignes donnent les états finaux
    for(size_t i = 0; i < at.nb_finaux; i++){
        do{ 
          getline (myfile,line);
        } while (line.empty() || line[0]=='#');
        iss.clear();
        iss.str(line);
         if((iss >> s).fail())
          continue;
        cerr << "s= " << s << endl;
        //TODO remplir finaux
        at.finaux.insert(s);
    }     

    // on alloue les vectors à la taille connue à l'avance pour éviter les resize dynamiques
    at.trans.resize(at.nb_etats);
    at.epsilon.resize(at.nb_etats);
    for(size_t i=0;i<at.nb_etats;++i)
      at.trans[i].resize(at.nb_symbs);   

  // lecture de la relation de transition 
    while(myfile.good()){
      line.clear();
      getline (myfile,line);
      if (line.empty() && line[0]=='#')
        continue;
      iss.clear();
      iss.str(line); 

      // si une des trois lectures echoue, on passe à la suite
      if((iss >> s).fail() || (iss >> a).fail() || (iss >> t).fail() || (a< ASCII_A ) || (a> ASCII_Z ))
        continue; 
              
      //test espilon ou non
      if ((a-ASCII_A) >= at.nb_symbs)
      {
        cerr << "s=" << s<< ", (e), t=" << t << endl;
        //TODO remplir epsilon
        at.epsilon[s].insert(t);
      }
      else
      {
        cerr << "s=" << s<< ", a=" << a-ASCII_A << ", t=" << t << endl;
        //TODO remplir trans
        at.trans[s][a-ASCII_A].insert(t);
      }
    }    
    myfile.close();
    return true; 
 }
  return false;
  // on ne peut pas ouvrir le fichier
}

////////////////////////////////////////////////////////////////////////////////

bool ContientFinal(const sAutoNDE& at,const etatset_t& e){
  for(etatset_t::const_iterator it=e.cbegin(); it != e.cend(); ++it)
  {
  //parcours des deux ensembles
  	for(etatset_t::const_iterator it1=at.finaux.cbegin(); it1 != at.finaux.cend(); ++it1)
		{
  		if(*it==*it1)
  		{
  		//si on trouve deux états égaux, on retourne vrai
  			return true;
			}	
		}
	}
  return false;
}

////////////////////////////////////////////////////////////////////////////////

bool EstDeterministe(const sAutoNDE& at){
	for(size_t i=0;i<at.nb_etats;++i)
	{
		if(at.epsilon[i].size()>1)
			return false;
		// si pour un état donné, on peut accéder a plusieurs états avec epsilon on retourne faux
		for(size_t j=0;j<at.nb_symbs;++j)
		{
		// on parcours la table de transition 
      if(at.trans[i][j].size()>1) 
      	return false;
      	// si pour un état donné et un caractère donné, l'ensemble d'états auquels on peut accéder est supérieur a 1
  			// on retourne faux
    }
	}
  return true;
}



////////////////////////////////////////////////////////////////////////////////

void Fermeture(const sAutoNDE& at, etatset_t& e){
  // Cette fonction clot l'ensemble d'états E={e_0, e_1, ... ,e_n} passé en 
  // paramètre avec les epsilon transitions
  for(etatset_t::const_iterator it=e.cbegin(); it != e.cend(); ++it)
  {
  		for(etatset_t::const_iterator it1=at.epsilon[*it].cbegin(); it1 != at.epsilon[*it].cend(); ++it1)
  		{
  			// on parcours epsilon avec les états de l'ensembles e, on ajoute dans e 
  			//les états auquels on peut avoir acces a partir de ces états
  			e.insert(*it1);
  		}
	}
}


////////////////////////////////////////////////////////////////////////////////

etatset_t Delta(const sAutoNDE& at, const etatset_t& e, symb_t c){
  //TODO sur la base de celle pour le cas sans transitions spontanées, 
  // définir cette fonction en utilisant Fermeture
  etatset_t p,q;
  p=e;
  //on effectue la fermeture de l'ensemble e, et on l'enregistre dans l'ensemble d'états p
  Fermeture(at,p);
  for(etatset_t::const_iterator it=p.cbegin(); it != p.cend(); ++it)
  {
  	// on parcours l'ensemble des états de p apres fermeture
  	if(!(at.trans[*it][c-ASCII_A].empty()))
  		q.insert(at.trans[*it][c-ASCII_A].begin(),at.trans[*it][c-ASCII_A].end());
  		// on insère dans l'ensemble d'états q, les états auquels on peut avoir acces a partir d'un des états de p
  		// avec le caractère c
  }
  Fermeture(at,q);
  // on effectue la fermeture de l'ensemble d'états obtenus
  return q;
}

////////////////////////////////////////////////////////////////////////////////

bool Accept(const sAutoNDE& at, string str){
  etatset_t p;
  p.insert(at.initial);  
  // on prend l'état initial dans l'ensemble
  for (size_t i=0;i<str.size();i++)
  {
  // on parcourt la chaine de caractères
        p=Delta(at,p,str[i]);
        // on retient l'ensemble d'états auquels on peut accéder
  }
  return (ContientFinal(at, p));
  // si apres le parcours de la chaine l'ensemble d'états p contient un des états finaux, on retourne vrai
}


////////////////////////////////////////////////////////////////////////////////

void Test_fcts_Auto(const sAutoNDE& at)
{
	cout << " Test de la fct : ContientFinal" << endl;
	etatset_t p;
	p.insert(1);
	p.insert(2);
	if (ContientFinal(at,p))
		cout << " l'ensemble des états contient un des états finaux"<<endl;
	else
		cout << " l'ensemble des états ne contient pas un des états finaux"<<endl;
	
	cout << " Test de la fct : EstDeterministe" << endl;
	if (EstDeterministe(at))
		cout << " l'automate est détérministe"<<endl;
	else
		cout << " l'automate n'est pas détérministe"<<endl;
	
	cout << " Test de la fct Delta: " << endl;
	p.insert(2);
	p.insert(3);
	cout <<"les éléments de l'ensemble avant l'appel de Delta sont = {";
  for(etatset_t::iterator it=p.begin(); it!=p.end(); ++it){
    cout << " "<<*it<< " " ;
  }
  cout <<"}"<<endl;
	p=Delta(at,p,'b');
  cout <<"les éléments de l'ensemble après l'appel de Delta sont = {";
  for(etatset_t::iterator it=p.begin(); it!=p.end(); ++it){
    cout << " "<<*it<< " " ;
  }
  cout <<"}"<<endl;
  
	cout << " Test de la fct Accept: " << endl;
	int x=1;
	string s;
	while(x)
	{
		cout<<"veuillez entrer un mot a tester dans l'automate :"<<endl;
		cout<<"Entrez (q) pour quitter"<<endl;
		cin>>s;
		if(s=="q")
			x=0;
		else
		{
			if(Accept(at,s))
			{
				cout<<"le mot '" << s << "' est accepté " << endl;
			}
			else
				cout<<"le mot '" << s << "' n'est pas accepté " << endl;
		}
		
	}
}

////////////////////////////////////////////////////////////////////////////////

int main( int argc, char* argv[] ){
  string path, str;
  bool r;
  sAutoNDE at;
  
  cout << "***TP LIF 15 ***" << endl;  
 
  if(argc > 1)
    path.assign(argv[1]);
  else
    path = "./exempleNDE.txt"; 
  
  if(argc > 2)
    str.assign(argv[2]);
  else
    str = "";

  if (!FromFile(at, path)){
    cerr << "Erreur de lecture du fichier " << path << endl;
  }else{
    cerr << "Automate déterministe ? " << EstDeterministe(at) << endl;
    r = Accept(at, str);
    cout << "'" << str  <<  "' est accepté ? " << r << endl;
    Test_fcts_Auto(at);// Test de l'ensemble des fonctions du programme avec menu pour entrer les mots
  }
    
  return EXIT_SUCCESS;
}
